#include "swapper.h"

namespace Packing
{
	Swapper::Swapper(std::vector<Packing_polygon*>& polytopes, Polygon_triangulation& triangulation)
		: polygon_set(polytopes), pt(triangulation), rand_gen(std::time(0))
	{
	}

	void Swapper::swap()
	{
		std::cout<<"Start swapping...\n";
		// find the first p% polygons with the largest space around them

		// for each polygon, calculate the space around it
		// for the first experiment, we only use the 1-ring neighboring faces around each polygon
		std::map< double, unsigned int, std::greater<double> > area_index;
		std::vector<double> surround_area(polygon_set.size(), 0.0);
		for (Polygon_triangulation::Face_iterator fit = pt.faces_begin(); fit != pt.faces_end(); ++fit)
		{
			if (pt.is_infinite(fit))	continue;
			if (!pt.is_intergroup_face(fit))	continue;
			Polygon_triangulation::Vertex_handle v[] = {fit->vertex(0), fit->vertex(1), fit->vertex(2)};
			double area = std::fabs(CGAL::area(v[0]->point(), v[1]->point(), v[2]->point()));
			std::set<int> included;
			for (int i = 0; i < 3; i++)
			{
				if (v[i]->group_id < 0)	continue;

				if (included.find(v[i]->group_id) == included.end())
				{
					surround_area[v[i]->group_id] += area;
					included.insert(v[i]->group_id);
				}
			}
		}
		for (unsigned int i = 0; i < surround_area.size(); i++)
			area_index.insert(std::make_pair(surround_area[i]/polygon_set[i]->area(), i));
		double partition = 0.25;
		unsigned int n = polygon_set.size()*partition + 1;
		std::map< double, unsigned int, std::greater<double> >::iterator it = area_index.begin();

		// for illustration
		std::vector<unsigned int> to_be_swapped(n);
		for (unsigned int i = 0; i < n; i++, ++it)
		{
			polygon_set[it->second]->large_neighbor_room(true);
			to_be_swapped[i] = it->second;
		}
		for (unsigned int i = n; i < polygon_set.size(); i++, ++it)
		{
			polygon_set[it->second]->large_neighbor_room(false);
		}

		// match
		std::vector< std::vector< Match_info_item<unsigned int> > > similarity_mat(n);
		std::for_each( similarity_mat.begin(), similarity_mat.end(), std::bind2nd(std::mem_fun_ref(&std::vector< Match_info_item<unsigned int> >::resize), n));

		// compute similairy of each polygon-hole pair
		for (unsigned int i = 0; i < n; i++)
		{
			// perimeter of the hole
			const Polygon_triangulation::Vert_group& vg = pt.vertex_at_group(to_be_swapped[i]);

			// extract the hole
			std::vector<Polygon_triangulation::Segment> outline;
			for (unsigned int j = 0; j < vg.size(); j++)
			{
				if (vg[j]->cat_vtx.size() > 1)
				{
					for (unsigned int k = 0; k < vg[j]->cat_vtx.size()-1; k++)
						outline.push_back(Polygon_triangulation::Segment(vg[j]->cat_vtx[k], vg[j]->cat_vtx[k+1]));
				}
			}
			Polygon_matcher pm(outline);
			for (unsigned int j = 0; j < n; j++)
			{
				const Packing_polygon* p = polygon_set[to_be_swapped[j]];
				similarity_mat[i][j] = pm.affine_match(*p, to_be_swapped[j]);
			}
		}
		std::vector<bool> hole_matched(n, false), polygon_matched(n, false);
		std::vector< std::pair<unsigned int, unsigned int> > replace_pair;
		replace_pair.reserve(n);
		while (true)
		{
			double sim_dist = std::numeric_limits<double>::max();
			unsigned int h, p; //hole-polygon pair with the maximum similarity
			for (unsigned int i = 0; i < n; i++)
			{
				if (!hole_matched[i])
				{
					for (unsigned int j = 0; j < similarity_mat[i].size(); j++)
					{
						if (!polygon_matched[j] && similarity_mat[i][j].error < sim_dist)
						{
							h = i;
							p = j;
							sim_dist = similarity_mat[i][j].error;
						}
					}
				}
			}
			if (sim_dist == std::numeric_limits<double>::max())
				break;
			// place polygon to_be_moved[p] to the hole to_be_moved[h]
			replace_pair.push_back(std::make_pair(h, p));
			hole_matched[h] = polygon_matched[p] = true; // this hole and polygon have already been considered
		}

		//replace
		std::vector<Packing_polygon> to_replace_list;
		to_replace_list.reserve(n);
		for (unsigned int i = 0; i < n; i++)
		{
			unsigned int p = to_be_swapped[replace_pair[i].second];
			const Packing_polygon& to_replace = *polygon_set[p];
			const Match_info_item<unsigned int>& match = similarity_mat[replace_pair[i].first][replace_pair[i].second];
			// NOTE: overlap may occure due to this transformation
			to_replace_list.push_back(transform(match.t, to_replace));
			//to_replace_list.back().set_scale_factor(match.scale*to_replace.get_scale_factor());
			double sr = match.scale*to_replace.get_scale_factor();
			double f = 1.0;
			while (sr*f > 1.0)	f *= 0.6;
			if (f < 1.0)
				to_replace_list.back().relative_scale(f);
			to_replace_list.back().set_scale_factor(f*sr);
			//to_replace_list.back().relative_scale(0.6);
			//to_replace_list.back().set_scale_factor(0.6*match.scale*to_replace.get_scale_factor());
			//if (to_replace_list.back().get_scale_factor() > 1.0)
			//{
			//	to_replace_list.back().relative_scale(0.6);
			//}
		}
		for (unsigned int i = 0; i < n; i++)
		{
			unsigned int h = to_be_swapped[replace_pair[i].first];
			*polygon_set[h] = to_replace_list[i];
		}
		std::cout<<"Swapping ends.\n";
	}

	void Swapper::random_shuffle()
	{
		std::vector<unsigned int> shuffle_indices(polygon_set.size());
		for (unsigned int i = 0; i < polygon_set.size(); i++)
			shuffle_indices[i] = i;
		// randomly take some number of polygons and shuffle them
		std::random_shuffle(shuffle_indices.begin(), shuffle_indices.end());
		const unsigned int N = polygon_set.size()*0.1 + 1;
		std::vector<unsigned int> from(N);
		std::copy(shuffle_indices.begin(), shuffle_indices.begin()+N, from.begin());
		std::vector< std::pair<unsigned int, unsigned int> > swap_pairs;

		while (swap_pairs.empty())
		{
			swap_pairs.clear();
			swap_pairs.reserve(N);
			std::random_shuffle(shuffle_indices.begin(), shuffle_indices.begin()+N);
			for (unsigned int i = 0; i < N; i++)
			{
				if (from[i] != shuffle_indices[i])
				{
					swap_pairs.push_back(std::make_pair(from[i], shuffle_indices[i]));
				}
			}
		}

		// do the shuffle
		std::vector<Packing_polygon> to_replace(swap_pairs.size());
		for (unsigned int i = 0; i < swap_pairs.size(); i++)
		{
			to_replace[i] = *polygon_set[swap_pairs[i].first];
		}
		for (unsigned int i = 0; i < swap_pairs.size(); i++)
		{
			Packing_polygon::Point_2 cfrom = to_replace[i].centroid(), cto = polygon_set[swap_pairs[i].second]->centroid();
			Packing_polygon::Transformation_2 move(CGAL::TRANSLATION, Packing_polygon::Vector(cfrom, cto));
			*polygon_set[swap_pairs[i].second] = transform(move, to_replace[i]);
			polygon_set[swap_pairs[i].second]->set_scale_factor(to_replace[i].get_scale_factor());
		}
		for (unsigned int i = 0; i < polygon_set.size(); i++)
		{
			polygon_set[i]->scale(0.6);
		}
		//for (unsigned int i = 0; i < swap_pairs.size(); i++)
		//	polygon_set[swap_pairs[i].second]->scale(0.6);
	}

	void Swapper::fluctuate_rotation()
	{			
		// for each polygon, calculate the space around it
		// for the first experiment, we only use the 1-ring neighboring faces around each polygon
		std::map< double, unsigned int, std::greater<double> > area_index;
		std::vector<double> surround_area(polygon_set.size(), 0.0);
		for (Polygon_triangulation::Face_iterator fit = pt.faces_begin(); fit != pt.faces_end(); ++fit)
		{
			if (pt.is_infinite(fit))	continue;
			if (!pt.is_intergroup_face(fit))	continue;
			Polygon_triangulation::Vertex_handle v[] = {fit->vertex(0), fit->vertex(1), fit->vertex(2)};
			double area = std::fabs(CGAL::area(v[0]->point(), v[1]->point(), v[2]->point()));
			std::set<int> included;
			for (int i = 0; i < 3; i++)
			{
				if (v[i]->group_id < 0)	continue;

				if (included.find(v[i]->group_id) == included.end())
				{
					surround_area[v[i]->group_id] += area;
					included.insert(v[i]->group_id);
				}
			}
		}
		for (unsigned int i = 0; i < surround_area.size(); i++)
			area_index.insert(std::make_pair(surround_area[i]/polygon_set[i]->area(), i));
		double partition = 0.1;
		unsigned int N = polygon_set.size()*partition + 1;
		std::map< double, unsigned int, std::greater<double> >::iterator it = area_index.begin();

		const float f = 0.25f;
		boost::random::uniform_real_distribution<float> uni_distr(-f*180.0f, f*180.0f);
		boost::variate_generator< boost::random::mt19937&, boost::random::uniform_real_distribution<float> > gen(rand_gen, uni_distr);

		// select which polygons are to be rotated
		//std::vector<unsigned int> shuffle_indices(polygon_set.size());
		//for (unsigned int i = 0; i < polygon_set.size(); i++)
		//	shuffle_indices[i] = i;
		//// randomly take some number of polygons and shuffle them
		//std::random_shuffle(shuffle_indices.begin(), shuffle_indices.end());
		//const float partition = 0.2;
		//const unsigned int N = polygon_set.size()*partition + 1;
		for (unsigned int i = 0; i < N; i++, ++it)
		{
			polygon_set[it->second]->self_rotate(gen());
			polygon_set[it->second]->scale(0.6);
		}
	}
}